//class Solution {
//public:
//    bool vis[310][310] = { 0 };
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    int m, n;
//    int numIslands(vector<vector<char>>& grid) {
//        m = grid.size(), n = grid[0].size();
//        int ret = 0;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == '1' && !vis[i][j])
//                {
//                    ret++;
//                    vis[i][j] = true;
//                    dfs(grid, i, j);
//                }
//            }
//        }
//        return ret;
//    }
//
//    void dfs(vector<vector<char>>& grid, int i, int j)
//    {
//        for (int k = 0; k < 4; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
//            {
//                vis[x][y] = true;
//                dfs(grid, x, y);
//            }
//        }
//    }
//};




class Solution {
public:
    int findLongestNode(int u, vector<int>& parent, vector<vector<int>>& adj) 
    {

        int n = adj.size();
        queue<int> qu;
        vector<bool> visit(n);
        qu.emplace(u);
        visit[u] = true;
        int node = -1;

        while (!qu.empty())
        {
            int curr = qu.front();
            qu.pop();
            node = curr;
            for (auto& v : adj[curr]) 
            {
                if (!visit[v]) 
                {
                    visit[v] = true;
                    parent[v] = curr;
                    qu.emplace(v);
                }
            }
        }
        return node;
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges)
    {
        if (n == 1) 
        {
            return { 0 };
        }
        vector<vector<int>> adj(n);
        for (auto& edge : edges) 
        {
            adj[edge[0]].emplace_back(edge[1]);
            adj[edge[1]].emplace_back(edge[0]);
        }

        vector<int> parent(n, -1);
        int x = findLongestNode(0, parent, adj);
        int y = findLongestNode(x, parent, adj);
        vector<int> path;
        parent[x] = -1;
        while (y != -1) 
        {
            path.emplace_back(y);
            y = parent[y];
        }
        int m = path.size();
        if (m % 2 == 0)
        {
            return { path[m / 2 - 1], path[m / 2] };
        }
        else
        {
            return { path[m / 2] };
        }
    }
};